package nku.csc364;

public class AVLTree{
	
	private AVLNode root;
	
	public AVLTree(){
		root = null;
	}
	
	public void setRoot(AVLNode node){
		root = node;
	}
	
	public AVLNode getRoot(){
		return root;
	}
	
	
	public void insert(Object temp, String key) {
		
		//if tree is empty when adding node it just places it at the root
		if (root == null){
			root = new AVLNode((Comparable)temp, null, null, null);
		}

		//otherwise it iterates to see where the node goes and places it there
		else {
			boolean done = false;
			AVLNode current = root;
			while (!done) {
				
				// condition to check if its smaler or bigger then 
				// current node if its smaller it iterates left
				// otherwise it iterates to the right... 
				if ((current.getData()).compareTo(key) > 0 ) {
					if (current.getLeft() == null) {
						current.setLeft(new AVLNode((Comparable) temp, null, null, current));
						checkBalance(current);
						done = true;	
					}
					else{
						current = current.getLeft();
					}
				}
				else {
					if (current.getRight() == null) {
						current.setRight(new AVLNode((Comparable)temp, null, null, current));
						checkBalance(current);
						done = true;
					}
					else
						current = current.getRight();
				}
			}
			//System.out.println(current.getData());
		}
		
	}

	//Searches for the given social security
	public Object find(String key) {
		
		Object foundData = null;     //index to see if the given social is found
		AVLNode current = root; //starts current off at root
		
		//Goes through the tree to search the tree
		while (current != null && (current.getData().compareTo(key) != 0)) {
		
			if (current.getData().compareTo(key) > 0)
				current = current.getLeft();
			else
				current = current.getRight();
		}
		
		//If the ssn is found returns index
		if (current != null){
			foundData = current.getData();
		}
		
		return foundData;
	}

	// Removes a node that has same ssn
	public boolean delete(String key) {
		
		AVLNode current = root;
		AVLNode parent = null;
		boolean answer = false;
		

		// Traverse to the node to be removed.
		while (current != null && (current.getData().compareTo(key) != 0)) {
			parent = current;
			if (current.getData().compareTo(key) > 0)
				current = current.getLeft();
			else
				current = current.getRight();
		}

		if (current != null) {
			// If this is a leaf node, set the parent's
			// reference to null to remove it.
			if (current.getLeft() == null && current.getRight() == null) {
				if (current == parent.getLeft())
					parent.setLeft(null);
				else
					parent.setRight(null);
				answer = true;
				checkBalance(parent);
			}

			// If it only has one child, point the parent
			// at current's child to remove it.
			else if (current.getLeft() == null) {
				if (current == parent.getLeft())
					parent.setLeft(current.getRight());
				else
					parent.setRight(current.getRight());
				answer = true;
				checkBalance(parent);
			} else if (current.getRight() == null) {
				if (current == parent.getLeft())
					parent.setLeft(current.getLeft());
				else
					parent.setRight(current.getLeft());
					checkBalance(parent);
				answer = true;
				checkBalance(parent);
			}
			
			// Node to be removed has two children. Find
			// the highest value in the left subtree, and
			// copy the value to this node, then remove
			// that (rightmost) node.
			else {
				AVLNode swap = current.getLeft();
				parent = current;
				while (swap.getRight() != null) {
					parent = swap;
					swap = swap.getRight();
				}
				Object tempData = swap.getData();
				delete(swap.getData().toString(), current);
				current.setData((Comparable)tempData);
				answer = true;
				checkBalance(swap.getParent());
			}
		}
		
		return answer;
	}
	
	public boolean delete(String ssn, AVLNode current) {
		// I am missing to change the parents here..... i haven't gotten to fix this
		// since my insert still won't work...
		
		AVLNode swap = current.getLeft();
		AVLNode parent = swap;
		while (swap.getRight() != null) {
					parent = swap;
					swap = swap.getRight();
		}
		parent.setRight(null);
		return true;
	
	}
	
	public void checkBalance(AVLNode nodecheck){
		if (nodecheck == null)
			return;
		else {
			if((maxHeight(nodecheck.getRight()) - maxHeight(nodecheck.getLeft())) > 1){
				leftRotate(nodecheck);
			}
			else if((maxHeight(nodecheck.getRight()) - maxHeight(nodecheck.getLeft())) < -1){
				rightRotate(nodecheck);
			}
			if(nodecheck.getParent() != null){
				checkBalance(nodecheck.getParent().getParent());
			}
		}
	}
	
	public void leftRotate(AVLNode node){
		System.out.println("left rotate");
		AVLNode child = node.getRight();
		AVLNode temp = child.getLeft();
		if (child.getLeft() == null){
			if(node.getParent() == null){
				root = child;
				child.setParent(null);
			}
			else{
				if(node.getParent().getLeft() == node){
					node.getParent().setLeft(child);
					child.setParent(node.getParent());
					node.setParent(child);
					
				}
				else{
					node.getParent().setRight(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				child.setLeft(node);
				child.getLeft().setRight(null);
			}
		}
		else{
			if(node.getParent() == null){
				root = child;
				child.setParent(null);
			}
			else {
				if(node.getParent().getLeft() == node){
					node.getParent().setLeft(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				else{
					node.getParent().setRight(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				child.setLeft(node);
				child.getLeft().setRight(temp);
			}
		}
			
		
	}
	
	public void rightRotate(AVLNode node){
		System.out.println("right rotate");
		AVLNode child = node.getLeft();
		AVLNode temp = child.getRight();
		if(child.getRight()==null){
			if(node.getParent() == null){
				root = child;
				child.setParent(null);
			}
			else{
				if(node.getParent().getLeft() == node){
					node.getParent().setLeft(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				else{
					node.getParent().setRight(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				child.setRight(node);
				child.getRight().setLeft(null);
			}
		}
		else{
			if(node.getParent() == null){
				root = child;
				child.setParent(null);
			}
			else{
				if(node.getParent().getLeft() == node){
					node.getParent().setLeft(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				else{
					node.getParent().setRight(child);
					child.setParent(node.getParent());
					node.setParent(child);
				}
				child.setRight(node);
				child.getRight().setLeft(temp);
			}
		}
		
	}
	
	
	public int maxHeight(AVLNode node){
		if(node == null){
			return 0;
		}
		
		int height = 1;
		if (node.getRight() == null && node.getLeft() == null)
			return height;
		else if(node.getRight() == null){
			return 1 + (Integer)maxHeight(node.getLeft());
		}
		else if (node.getLeft() == null){
			//System.out.println(maxHeight(node.getRight()));
			return 1 + (Integer)maxHeight(node.getRight());
		}
		else{
			int leftHeight = 1 + maxHeight(node.getLeft());
			int rightHeight = 1 + maxHeight(node.getRight());
			if (leftHeight > rightHeight)
				return leftHeight;
			else 
				return rightHeight;
		}
	}

//	public int minHeight(AVLNode node){
//		if(node == null)
//			return 0;
//		int height = 1;
//		if(node.getRight() == null || node.getLeft() == null){
//			return height;
//		}
//		else{
//			int leftHeight = 1 + minHeight(node.getLeft());
//			int rightHeight = 1 + minHeight(node.getRight());
//			if (leftHeight < rightHeight)
//				return leftHeight;
//			else 
//				return rightHeight;
//		}
//		
//	}
	
//	public int height(AVLNode node){
//		int height = 0;
//		return height(height, node);
//	}
//	
//	public int height(int height, AVLNode node){
//		if (node == null){
//			return 0;
//		}
//		if ((node.getLeft() == null) && (node.getRight() == null)){
//			return height;
//		}
//		else if (node.getLeft() == null){
//			return height(height + 1, node.getRight());
//		}
//		else if (node.getRight() == null){
//			return height(height + 1, node.getLeft());
//		}
//		else{
//			int leftHeight = height(height + 1, node.getLeft());
//			int rightHeight = height(height + 1, node.getRight());
//			if (leftHeight > rightHeight)
//				return leftHeight;
//			else 
//				return rightHeight;
//		}
//	}
		

	//Clears AVL Tree just sets root to null 
	public void clear(){
		root = null;
	}
	

}